import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 20
 * Time: 11:22
 */
//力扣496。下一个更大元素I
class Solution1 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = nums2.length - 1; i >= 0; i--) {
            while(!stack.isEmpty() && nums2[i] >= stack.peek()) {
                stack.pop();
            }
            map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
            stack.push(nums2[i]);//维护一个从栈顶到栈低单调递增的栈
        }
        int[] nums = new int[nums1.length];
        for(int j = 0; j < nums1.length; j++) {
            nums[j] = map.get(nums1[j]);
        }
        return nums;
    }
}
